package com.mid;

import java.util.Stack;

/**
 * Created by Lxk on 2020/2/17.
 */
public class Solution331 {

    private boolean isTree(String[] preorder) {
        if (preorder.equals("#")) {
            return true;
        }
        Stack<String> stack = new Stack<>();
        stack.push(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            stack.push(preorder[i]);
            while (stack.size() >= 2 && stack.peek().equals("#") && stack.get(stack.size() - 2).equals("#")) {
                stack.pop();
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
                stack.push("#");
            }
            if (stack.isEmpty()) {
                return false;
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }

    public boolean isValidSerialization(String preorder) {
        String[] strArr = preorder.split(",");
        return isTree(strArr);
    }

    public static void main(String[] args) {
        String str = "9,#,92,#,#";
        Solution331 solution331 = new Solution331();
        System.out.println(solution331.isValidSerialization(str));
    }

}
